#include <vector>
#include <stack>
#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode() : val(0), left(nullptr), right(nullptr)
    {}
    TreeNode(int val) : val(val), left(nullptr), right(nullptr)
    {}
    TreeNode(int val, TreeNode * left, TreeNode * right) : val(val), left(left), right(right)
    {}
};

class Solution 
{
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
		vector<int> result;
		stack<pair<TreeNode*, bool>> st;
		if(root == nullptr)
		{
			return result;
		}
		st.push(make_pair(root, false));
		while (!st.empty())
		{
			auto node = st.top().first;
			auto isVisited = st.top().second;
			st.pop();
			if(isVisited)
			{
				result.push_back(node->val);
			}
			else
			{
				if(node->right != nullptr)
				{
					st.push(make_pair(node->right, false));
				}
				if(node->left != nullptr)
				{
					st.push(make_pair(node->left, false));
				}
				st.push(make_pair(node, true));
			}
		}
		return result;
    }
};

static void printVector(const vector<int> & vec)
{
	cout << "[";
	for (size_t i = 0; i < vec.size(); i++)
	{
		cout << vec[i];
		if (i + 1 < vec.size()) cout << ",";
	}
	cout << "]" << endl;
}

int main()
{
	Solution solution;

	// 用例1：题目示例1  root = [1,null,2,3]
	TreeNode * r1 = new TreeNode(1);
	r1->right = new TreeNode(2);
	r1->right->left = new TreeNode(3);
	vector<int> ans1 = solution.preorderTraversal(r1);
	cout << "用例1 实际: ";
	printVector(ans1);
	cout << "用例1 预期: [1,2,3]\n" << endl;

	// 用例2：空树
	TreeNode * r2 = nullptr;
	vector<int> ans2 = solution.preorderTraversal(r2);
	cout << "用例2 实际: ";
	printVector(ans2);
	cout << "用例2 预期: []\n" << endl;

	// 用例3：单节点
	TreeNode * r3 = new TreeNode(42);
	vector<int> ans3 = solution.preorderTraversal(r3);
	cout << "用例3 实际: ";
	printVector(ans3);
	cout << "用例3 预期: [42]\n" << endl;

	// 用例4：左斜树  [1,2,3,null,...]
	TreeNode * r4 = new TreeNode(1);
	r4->left = new TreeNode(2);
	r4->left->left = new TreeNode(3);
	vector<int> ans4 = solution.preorderTraversal(r4);
	cout << "用例4 实际: ";
	printVector(ans4);
	cout << "用例4 预期: [1,2,3]\n" << endl;

	// 用例5：右斜树  [1,null,2,null,3]
	TreeNode * r5 = new TreeNode(1);
	r5->right = new TreeNode(2);
	r5->right->right = new TreeNode(3);
	vector<int> ans5 = solution.preorderTraversal(r5);
	cout << "用例5 实际: ";
	printVector(ans5);
	cout << "用例5 预期: [1,2,3]\n" << endl;

	// 用例6：一般复杂树  [1,2,3,4,5,6,7]
	TreeNode * r6 = new TreeNode(1);
	r6->left = new TreeNode(2);
	r6->right = new TreeNode(3);
	r6->left->left = new TreeNode(4);
	r6->left->right = new TreeNode(5);
	r6->right->left = new TreeNode(6);
	r6->right->right = new TreeNode(7);
	vector<int> ans6 = solution.preorderTraversal(r6);
	cout << "用例6 实际: ";
	printVector(ans6);
	cout << "用例6 预期: [1,2,4,5,3,6,7]\n" << endl;

	return 0;
}